/*
* 2010
* Author: Kuznetsov Kirill<kirill.kuznets@gmail.com>
* FasGenetic class realisation
*/

#include "fas_genetic.h"
#include <boost/graph/adjacency_list.hpp>
#include <ctime>
#include <boost/graph/random.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/bind.hpp>
#include <functional>
#include <algorithm>
#include <boost/graph/copy.hpp>

void FasGenetic::CreateFirstGen(const Graph& g, size_t gen_size, Generation& crnt_gen)
{
	LogStream logcout( &cout);
	logcout << "Creating first generation" << endl;

	const size_t vnum = num_vertices(g);
	mt19937 rng;
	rng.seed(uint32_t(time(0)));
	//creating necessary number of random numerations
	for (size_t j = 0; j < gen_size; j++) {
		GenNumeration n;
		for(size_t num = 0; num < vnum; num++){
			//assign current number to random vertex
			pair<GenNumeration::iterator, size_t> ins;
			do {
				//warning
				Vertex v = random_vertex(g, rng);
				ins = n.insert(make_pair(v, num));
			} while( !ins.second);
		}	
		AddGenNum(crnt_gen, g, n);
	}
	
	logcout << "Done." << endl;
}
void FasGenetic::PrintNum (const GenNumeration& n){
	LogStream logcout( &cout);
	GenNumeration ::const_iterator vi,ve;
	logcout << "numeration: ";
	for(vi = n.begin(); vi != n.end(); vi++)
		logcout << vi->second << " ";
	logcout << endl;
}
void FasGenetic::Crossover(const GenNumeration& mom,const GenNumeration& dad, 
						   const Graph& worker, GenNumeration& child)
{
	//	logcout << "Performing Crossover" <<endl;
	size_t num = num_vertices(worker);
	size_t pos = 0;
	for (size_t i = 0, m_pos = 0, d_pos = num - 1; i < num; ++i) {
		if (i % 2 == 0) {								//on even steps take mothers genes
			pos = i / 2;								//begining from the first ones
			while(!Inherited( pos, child, mom, m_pos))	//trying to inherit selected gene
				++m_pos;								//and move next in proper direction if it has
		} else {										//on odd steps take fathers genes			
			pos = num - 1 - i / 2;						//begining from the last ones
			while(!Inherited( pos, child, dad, d_pos))
				--d_pos;
		}
	}
	//return child;
}
bool FasGenetic::Inherited(size_t i, GenNumeration& child, const GenNumeration& parent,size_t parent_pos){
	Vertex v = FindVertex(parent, parent_pos);
	pair<GenNumeration::iterator, bool> ins = child.insert(make_pair(v, i));
	return ins.second;
}

void FasGenetic::Mutation(const GenNumeration& mutant, const Graph& worker, GenNumeration& child)
{
	//	logcout << "Performing Mutation" <<endl;

	//	srand((unsigned int)(time(NULL)));
	size_t vertices = num_vertices(worker);
	//choose two indexes i,j: 0<i<j<max index
	const size_t i = rand() % (vertices - 1); // 0 < i < max index
	const size_t j = rand() % (vertices - 1 - i) + i + 1; // i < j <= max index;

	GenNumeration ::const_iterator viter;
	//for all vertices v[k]: i < k <= j decrease their indexs by 1, v[i] place to j-th position
	for (viter = mutant.begin(); viter != mutant.end(); ++ viter) {
		size_t v_num = viter->second;
		if (v_num > i && v_num <= j) {
			child[viter->first] = v_num - 1;
		} else {
			child[viter->first] = v_num;
		}
	}	
	Vertex vi = FindVertex(mutant, i);
	child[vi] = j;	
	//return child;
}

void FasGenetic::NewOffspring(const Graph& worker, Generation& crnt_gen, size_t gen_size)
{
	//logcout << "Rising new generation" <<endl;
	//making new offspring
	Generation candidates = crnt_gen;
	srand((unsigned int)(time(NULL)));
	for (Generation::iterator mom = crnt_gen.begin(); mom != crnt_gen.end(); mom++) {
		//imitation of m_prob % mutation probability	
		int prob = rand() % 100;
		if (prob > m_prob ) {
			const GenNumeration& dad = RandomNumeration( crnt_gen, gen_size);
			GenNumeration child1, child2; 
			Crossover( dad, mom->second, worker, child1);
			Crossover( dad, mom->second, worker, child2);
			AddGenNum(candidates, worker, child1);
			AddGenNum(candidates, worker, child2);
		} else {
			GenNumeration child;
			Mutation(mom->second, worker, child);
			AddGenNum(candidates, worker, child);
		}
	}
	//logcout <<"Number of candidates: " << candidates.size() << endl;

	//making new generation of proper size from offspring elite
	Generation::iterator first, last;
	first = candidates.begin();
	last = candidates.begin();
	for(size_t i = 0; i < gen_size; ++i, ++last);
	crnt_gen = Generation(first, last);
}

void FasGenetic::AddGenNum(Generation& gen, const Graph& worker, const GenNumeration& gen_num){
	gen.insert(make_pair(EvalMetric(gen_num, worker), gen_num));
}

void FasGenetic::Evolution(const Graph& worker, size_t gen_size, size_t max_iters, 
						   Generation& crnt_gen)
{
	LogStream logcout( &cout);
	logcout << "Begining evolution" << endl;
	CreateFirstGen( worker, gen_size, crnt_gen);
	logcout << "Evolution complete on:"<< endl;

	//evolution continues for max_itera or until minimum quantity of leftward edges for some numeration 
	//is reached and due to standard ordering for size_t in multimap 
	//it is sufficient to check only first element in crnt_gen
	for (size_t i = 0; i < max_iters && (crnt_gen.begin())->first > min; ++i) {
		logcout << "             \r"<< (double)i / max_iters * 100 <<"% "<<"best fitness: " << crnt_gen.begin()->first ;
		NewOffspring( worker, crnt_gen, gen_size);
		// evolution completion in %
	}
	logcout <<  '\r' << "Evolution finished. Best: " << crnt_gen.begin()->first << endl;
}

//calculate number of leftward edges for given GenNumeration
size_t FasGenetic::EvalMetric(const GenNumeration& n, const Graph& worker)
{
	Edge_Iterator ei, ee;
	tie(ei, ee) = edges(worker);
	return count_if( ei, ee, bind( IsLeftward, n, _1, worker));

}

bool FasGenetic::IsLeftward(const GenNumeration& n, const Edge& e, const Graph& worker)
{
	Vertex begin = source(e, worker), end = target(e, worker);
	int b_num = -1, e_num = -1;
	//logcout<<begin<<" "<<n[begin]<<"->"<<n[end]<<" "<<end<<endl;
	for(GenNumeration::const_iterator it = n.begin(); it != n.end() || b_num < 0 || e_num < 0; ++it){
		if( it -> first == begin)
			b_num = it->second;		
		if( it -> first == end)
			e_num = it->second;
	}
	if (b_num != e_num)
			b_num = b_num;
	return b_num >= e_num;
}

//removing edges from FAS, thus removing cycles
void FasGenetic::RemoveCycles(Graph &worker, size_t gen_size, size_t max_iters)
{
	LogStream logcout( &cout);
	logcout << "Removing cycles..." << endl;

	Generation crnt_gen;
	Evolution(worker, gen_size, max_iters, crnt_gen);

	//warning
	list<Edge> fas;
	GenNumeration n = (crnt_gen.begin())->second;
	Edge_Iterator ei, ee;
	for (tie(ei,ee) = edges(worker); ei != ee; ei++) {
		if (IsLeftward(n, *ei, worker)) {
			fas.push_back(*ei);
		}
	}

	for (list<Edge>::iterator tmp = fas.begin(); tmp != fas.end(); tmp++) {
		remove_edge(*tmp, worker);
	}
}

Vertex FasGenetic::FindVertex(const GenNumeration& n, size_t num){
	GenNumeration::const_iterator ni = find_if ( n.begin(), n.end(), bind( NumBy, _1, num) );
	return ni ->first;
}
bool FasGenetic::NumBy( pair<Vertex, size_t> vert_num, size_t num){
	return vert_num.second == num;
}
const GenNumeration& FasGenetic::RandomNumeration(const Generation& gen, size_t gen_size){
	size_t num = rand() % gen_size, i;
	Generation::const_iterator it = gen.begin();
	for (i = 0; i < num && it != gen.end()--; i++, it++);
	return it->second;
}